package com.jp.algorithm;

public class LongestIncreaseSequence {

    static int staticMax = 0;

    public static int getLIS(int[] a, int n,int[] record) {
        if (n == 0) {
            return n + 1;
        }
        int max = 0;
        for (int i = 0; i < n; i++) {
            int l;
            if(record[i] == -1){
                l = getLIS(a, i,record);
                record[i]=l;
            }else{
                l=record[i];
            }

            if (l > max && a[i] < a[n])
                max = l;
        }
        if (max+1 > staticMax) {
            staticMax = max+1;
        }
        return max+1;
    }

    public static void getLISNoRecursive(int[] a,int[] record){
        record[0]=1;
        for(int i=1;i<a.length;i++){
            int max=0;
            for(int j=0;j<i;j++){
                if(record[j]>max && a[j]<a[i]){
                    max=record[j];
                }
            }
            record[i]=max+1;
            if((max+1)>staticMax)
                staticMax=max+1;
        }
    }


    public static void test() {
        staticMax=0;
        int[] a = {10, 9, 2, 5, 3, 7, 101,102, 18};
        int[] record = new int[a.length];
        for(int i=0;i<record.length;i++){
            record[i]=-1;
        }
        getLIS(a, a.length - 1,record);
        System.out.println("max:"+staticMax);
    }
    public static void test1() {
        staticMax=0;
        int[] a = {10, 9, 2, 5, 3, 7, 101,20, 18};
        int[] record = new int[a.length];
        for(int i=0;i<record.length;i++){
            record[i]=-1;
        }
        getLISNoRecursive(a,record);
        System.out.println("max:"+staticMax);
    }

    public static void main(String[] args) {
        test();
        test1();
    }
}
